package 剑指offer;

public class 手机屏幕解锁模式_调查 {
    public static void main(String[] args) {
        init(3,3 );
        System.out.println(solution(3, 3));
        System.out.println(sb);

    }

    static int[][] arr = new int[3][3];
    static StringBuilder sb = new StringBuilder();
    public static void init(int n, int m) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                count++;
                arr[i][j] = count;
            }
        }
    }
    public static int solution (int m, int n) {
//         递归实现
        int count = 0;
        n = n>9 ? 9 : n;
        for(int i=m;i<=n;i++) {
            boolean[][] flags = new boolean[3][3];
            for(int j=0;j<3;j++) {
                for(int t=0;t<3;t++) {
                    count += findNext(flags, j, t, 0, i);
                }
            }
        }
        return count;
    }

    public static int findNext(boolean[][] flags,int curRow, int curCol, int steps, int n) {
        int count = 0;
        steps ++;
        flags[curRow][curCol] = true;
//         步数走完返回
        if (steps == n) {
            System.out.println(sb.toString());
            sb = new StringBuilder(sb.substring(0, sb.length() - 1));
        }
        if(steps == n)

            return 1;

//         如果可以走，那么返回 1
        for(int i=0;i<3;i++) {
            for(int j=0;j<3;j++) {
                if(flags[i][j] == false && canStep(flags, curRow, curCol, i, j)) {
                    sb.append(arr[i][j]);
                    count += findNext(flags, i, j, steps, n);
//                     恢复状态
                    flags[i][j] = false;
                }
            }
        }
        flags[curRow][curCol] = false;
        return count;
    }

    public static boolean canStep(boolean[][] flags, int curRow, int curCol, int targetRow, int targetCol) {
//         在同一行
        if(curRow == targetRow) {
            int low = curCol < targetCol?curCol:targetCol;
            if(Math.abs(curCol - targetCol) >1 && flags[curRow][low+1] == false)
                return false;
        }
//         在同一列
        if(curCol == targetCol) {
            int low = curRow < targetRow?curRow:targetRow;
            if(Math.abs(curRow - targetRow) >1 && flags[low+1][curCol] == false)
                return false;
        }
//         斜对角
        if(Math.abs(curRow-targetRow)==2 && Math.abs(curCol-targetCol)==2 && flags[1][1] == false)
            return false;
        return true;
    }
}
